/**
 * 
 */
package string.passed;

import java.util.Arrays;

/**
 * @author Michael
 * @since 01/06/2013
 */

/**
 * '?' Matches any single character.
 * '*' Matches any sequence of characters
 * (including the empty sequence).
 * 
 * The matching should cover the entire input string (not partial).
 * 
 * The function prototype should be: bool isMatch(const char *s, const char *p)
 * 
 * Some examples: 
 * isMatch("aa","a") → false
 * isMatch("aa","aa") → true
 * isMatch("aaa","aa") → false
 * isMatch("aa", "*") → true 
 * isMatch("aa", "a*") → true 
 * isMatch("ab", "?*") → true 
 * isMatch("aab", "c*a*b") → false
 * 
 * Solution http://blog.csdn.net/hopeztm/article/details/8039777
 * http://blog.csdn.net/tingmei/article/details/8049926
 */
public class WildcardMatching {

	public static boolean isMatch(String s, String p) {
		// return isMatchRecursionHelp(s, p, 0, 0);
		return isMatchInterationHelp(s, p);
	}

	/**
	 * Greedy
	 * 
	 * @param s
	 * @param p
	 * @return
	 */
	public static boolean isMatchGreedy(String s, String p) {
		int sLen = s.length();
		int pLen = p.length();
		int si = 0; // current index in s
		int pi = 0; // current index in p
		int pStar = -1; // the last * index from now
		int sStar = 0; // the last index in s match the * in p

		while (si < sLen) {
			while (pi < pLen && p.charAt(pi) == '*') {
				pStar = pi++;
				sStar = si;
			}

			if (pi == pLen
					|| (s.charAt(si) != p.charAt(pi) && p.charAt(pi) != '?')) {
				if (pStar == -1) {
					return false;
				}
				si = ++sStar; // match 1 char in s
				pi = pStar + 1;
			} else {
				pi++;
				si++;
			}
		}

		while (pi < pLen && p.charAt(pi) == '*') {
			pi++;
		}

		return pi == pLen;
	}

	/**
	 * http://discuss.leetcode.com/questions/222/wildcard-matching
	 * DP
	 * 
	 *    s:  A  D  E  B
	 *    p:  A*
	 *       
	 *       0  1  2  3  4
	 *    0  f  f  f  f  t
	 *    1  t  t  t  t  t 
	 *    
	 *    	 0  1  2  3  4
	 *    0  f  f  f  f  f
	 *    1  t  t  t  t  t
	 * @param s
	 * @param p
	 * @return
	 */
	public boolean isMatchDP(String s, String p) {
		int sLen = s.length();
		int pLen = p.length();

		boolean[][] dp = new boolean[2][sLen + 1];
		dp[pLen % 2][sLen] = true;

		for (int pi = pLen - 1; pi >= 0; pi--) {
			Arrays.fill(dp[pi % 2], false);
			if (p.charAt(pi) == '*') {
				for (int si = sLen; si >= 0; si--) {
					if (dp[(pi + 1) % 2][si]) {
						for (; si >= 0; si--)
							dp[pi % 2][si] = true;
					}
				}
			} else {
				for (int si = sLen - 1; si >= 0; si--) {
					dp[pi % 2][si] = (p.charAt(pi) == s.charAt(si) || p
							.charAt(pi) == '?') && dp[(pi + 1) % 2][si + 1];
				}
			}
		}
		return dp[0][0];
	}

	public static boolean isMatchInterationHelp(String str, String pattern) {
		if (str == null || pattern == null)
			return false;

		int si = 0;// str index meet the most last * in pattern
		int pi = 0;// pattern index just after most last *
		boolean star = false;// meet star?
		int i = 0;// index

		while (i + si < str.length()) {
			if (pi + i == pattern.length()) {
				if (!star)
					return false;
				si++;
				i = 0;
				continue;
			}

			switch (pattern.charAt(pi + i)) {
			case '?':
				i++;
				break;
			case '*':
				star = true;
				pi += i;
				si += i;
				while (pi < pattern.length() && pattern.charAt(pi) == '*') {
					pi++;
				}
				if (pi == pattern.length())
					return true;
				i = 0;
				break;
			default:
				if (str.charAt(si + i) != pattern.charAt(pi + i)) {
					if (!star)
						return false;
					si++;
					i = 0;
				} else {
					i++;
				}
				break;
			}
		}

		pi += i;
		while (pi < pattern.length() && pattern.charAt(pi) == '*') {
			pi++;
		}

		return pi == pattern.length();
	}

	public static boolean isMatchRecursionHelp(String str, String pattern,
			int si, int pi) {
		if (str == null || pattern == null)
			return false;

		if (pattern.length() == pi)
			return str.length() == si;

		if (str.length() == si) {
			return pattern.charAt(pi) == '*' ? isMatchRecursionHelp(str,
					pattern, si, pi + 1) : false;
		}

		if (pattern.charAt(pi) != '*') {
			if (pattern.charAt(pi) == '?'
					|| pattern.charAt(pi) == str.charAt(si)) {
				return isMatchRecursionHelp(str, pattern, si + 1, pi + 1);
			} else {
				return false;
			}
		}

		return isMatchRecursionHelp(str, pattern, si + 1, pi)
				|| isMatchRecursionHelp(str, pattern, si, pi + 1);
	}

	/*
	 * '?' Matches any single character. '*' Matches zero or more characters.
	 * str: string to check pattern: pattern to match si: string index pi:
	 * pattern index
	 * 
	 * 
	 */
	public static boolean match(char[] str, char[] pattern, int si, int pi) {
		if (str == null || pattern == null)
			return false;

		// pattern characters have all been matched
		if (pattern.length == pi)
			return str.length == si;

		if (str.length == si)
			return pattern[pi] == '*' ? match(str, pattern, si, pi + 1) : false;

		// if current pattern character is not '*', must match current
		// characters
		if (pattern[pi] != '*') {
			// current characters match, go further for both
			if (str[si] == pattern[pi] || pattern[pi] == '?') {
				return match(str, pattern, si + 1, pi + 1);
			}
			// current characters don't match
			else {
				return false;
			}
		}

		// current pattern character is '*'
		return match(str, pattern, si + 1, pi)
				|| match(str, pattern, si, pi + 1);
	}

	// good for interview
	public static boolean match1(char[] str, char[] pattern, int si, int pi) {
		assert (str != null && pattern != null && si <= str.length && pi <= pattern.length);

		if (pi == pattern.length) {
			return si == str.length;
		}

		if (si == str.length) {
			return pattern[pi] == '*' ? match1(str, pattern, si, pi + 1)
					: false;
		}

		if (pattern[pi] != '*') {
			if (pattern[pi] == str[si] || pattern[pi] == '?') {
				return match1(str, pattern, si + 1, pi + 1);
			} else
				return false;
		}

		return match1(str, pattern, si + 1, pi)
				|| match1(str, pattern, si, pi + 1);
	}

	/**
	 * 
	 */
	public WildcardMatching() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String[] ss = { "", "aaaa", "a", "aa", "aa", "aa", "ab", "abcde",
				"aab", "ab" };
		String[] ps = { "*", "*a", "b", "a", "b*a", "*", "ab*", "ab?*e",
				"?a*b", "?*b" };
		for (int i = 0; i < ss.length; i++)
			System.out.println(ss[i] + ", " + ps[i] + ": "
					+ isMatchGreedy(ss[i], ps[i]));
	}

}
